<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Design Notes</title>
<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
<link rel="up" href="../intrusive.html" title="Chapter 16. Boost.Intrusive">
<link rel="prev" href="obtaining_same_type_reducing_space.html" title="Obtaining the same types and reducing symbol length">
<link rel="next" href="performance.html" title="Performance">
<meta name="viewport" content="width=device-width, initial-scale=1">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td>
<td align="center"><a href="../../../index.html">Home</a></td>
<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="obtaining_same_type_reducing_space.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../intrusive.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="performance.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="intrusive.design_notes"></a><a class="link" href="design_notes.html" title="Design Notes">Design Notes</a>
</h2></div></div></div>
<div class="toc"><dl class="toc">
<dt><span class="section"><a href="design_notes.html#intrusive.design_notes.performance_sensitive">Boost.Intrusive
      in performance sensitive environments</a></span></dt>
<dt><span class="section"><a href="design_notes.html#intrusive.design_notes.space_constrained">Boost.Intrusive
      in space constrained environments</a></span></dt>
<dt><span class="section"><a href="design_notes.html#intrusive.design_notes.basic_building_block">Boost.Intrusive
      as a basic building block</a></span></dt>
<dt><span class="section"><a href="design_notes.html#intrusive.design_notes.extending_intrusive">Extending
      Boost.Intrusive</a></span></dt>
</dl></div>
<p>
      When designing <span class="bold"><strong>Boost.Intrusive</strong></span> the following
      guidelines have been taken into account:
    </p>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="intrusive.design_notes.performance_sensitive"></a><a class="link" href="design_notes.html#intrusive.design_notes.performance_sensitive" title="Boost.Intrusive in performance sensitive environments">Boost.Intrusive
      in performance sensitive environments</a>
</h3></div></div></div>
<p>
        <span class="bold"><strong>Boost.Intrusive</strong></span> should be a valuable tool
        in performance sensitive environments, and following this guideline, <span class="bold"><strong>Boost.Intrusive</strong></span> has been designed to offer well known
        complexity guarantees. Apart from that, some options, like optional constant-time,
        have been designed to offer faster complexity guarantees in some functions,
        like <code class="computeroutput"><span class="identifier">slist</span><span class="special">::</span><span class="identifier">splice</span></code>.
      </p>
<p>
        The advanced lookup and insertion functions for associative containers, taking
        an arbitrary key type and predicates, were designed to avoid unnecessary
        object constructions.
      </p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="intrusive.design_notes.space_constrained"></a><a class="link" href="design_notes.html#intrusive.design_notes.space_constrained" title="Boost.Intrusive in space constrained environments">Boost.Intrusive
      in space constrained environments</a>
</h3></div></div></div>
<p>
        <span class="bold"><strong>Boost.Intrusive</strong></span> should be useful in space
        constrained environments, and following this guideline <span class="bold"><strong>Boost.Intrusive</strong></span>
        separates node algorithms and intrusive containers to avoid instantiating
        node algorithms for each user type. For example, a single class of red-black
        algorithms will be instantiated to implement all set and multiset containers
        using raw pointers. This way, <span class="bold"><strong>Boost.Intrusive</strong></span>
        seeks to avoid any code size overhead associated with templates.
      </p>
<p>
        Apart from that, <span class="bold"><strong>Boost.Intrusive</strong></span> implements
        some size improvements: for example, red-black trees embed the color bit
        in the parent pointer lower bit, if nodes are two-byte aligned. The option
        to forgo constant-time size operations can reduce container size, and this
        extra size optimization is noticeable when the container is empty or contains
        few values.
      </p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="intrusive.design_notes.basic_building_block"></a><a class="link" href="design_notes.html#intrusive.design_notes.basic_building_block" title="Boost.Intrusive as a basic building block">Boost.Intrusive
      as a basic building block</a>
</h3></div></div></div>
<p>
        <span class="bold"><strong>Boost.Intrusive</strong></span> can be a basic building
        block to build more complex containers and this potential has motivated many
        design decisions. For example, the ability to have more than one hook per
        user type opens the opportunity to implement multi-index containers on top
        of <span class="bold"><strong>Boost.Intrusive</strong></span>.
      </p>
<p>
        <span class="bold"><strong>Boost.Intrusive</strong></span> containers implement advanced
        functions taking function objects as arguments (<code class="computeroutput"><span class="identifier">clone_from</span></code>,
        <code class="computeroutput"><span class="identifier">erase_and_dispose</span></code>, <code class="computeroutput"><span class="identifier">insert_check</span></code>, etc.). These functions come
        in handy when implementing non-intrusive containers (for example, STL-like
        containers) on top of intrusive containers.
      </p>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="intrusive.design_notes.extending_intrusive"></a><a class="link" href="design_notes.html#intrusive.design_notes.extending_intrusive" title="Extending Boost.Intrusive">Extending
      Boost.Intrusive</a>
</h3></div></div></div>
<p>
        <span class="bold"><strong>Boost.Intrusive</strong></span> offers a wide range of containers
        but also allows the construction of custom containers reusing <span class="bold"><strong>Boost.Intrusive</strong></span>
        elements. The programmer might want to use node algorithms directly or build
        special hooks that take advantage of an application environment.
      </p>
<p>
        For example, the programmer can customize parts of <span class="bold"><strong>Boost.Intrusive</strong></span>
        to manage old data structures whose definition can't be changed.
      </p>
</div>
</div>
<div class="copyright-footer">Copyright © 2005 Olaf Krzikalla<br>Copyright © 2006-2015 Ion Gaztanaga<p>
        Distributed under the Boost Software License, Version 1.0. (See accompanying
        file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
      </p>
</div>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="obtaining_same_type_reducing_space.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../intrusive.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="performance.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
